#include <bits/stdc++.h>
using namespace std;
//lc46题，全排列
//
class Solution {
public:
    void dfs(vector<vector<int>>& ret,vector<int>&nums,           
                vector<int>& num,vector<bool>& use)
    {
        if(num.size()==nums.size())
        {
            ret.push_back(num);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(use[i])continue;
            else
            {
                num.push_back(nums[i]);
                use[i]=true;
                dfs(ret,nums,num,use);
                num.pop_back();
                use[i]=false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> use(nums.size(),false);
        vector<int> num;
        vector<vector<int>> ret;
        dfs(ret,nums,num,use);
        return ret;
    }
};


//lc47,去除重复的全排列
class Solution {
public:
    void dfs(vector<vector<int>>& ret,vector<int>&nums,           
                vector<int>& num,vector<bool>& use)
    {
        if(num.size()==nums.size())
        {
            ret.push_back(num);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(use[i])continue;
            if(i>0&&nums[i]==nums[i-1]&&!use[i-1])continue;
            else
            {
                num.push_back(nums[i]);
                use[i]=true;
                dfs(ret,nums,num,use);
                num.pop_back();
                use[i]=false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<bool> use(nums.size(),false);
        vector<int> num;
        sort(nums.begin(),nums.end());
        dfs(ret,nums,num,use);
        // set<vector<int>> s;
        // for(auto x:ret)
        // {
        //     s.insert(x);
        // }
        // ret.clear();
        // for(auto x:s)
        // {
        //     ret.push_back(x);
        // }
        return ret;
    }
};
